/*
 * 9.5.cpp
 *
 *  Created on: 2012-5-22
 *      Author: jawinton
 */

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>

using namespace std;

int count (int m, int n) {
	if (n == 1 || m == 0) return 1;
	if (m < n) return count(m, m);
	return count(m, n-1) + count(m-n, n);
}

int main(void) {
	int t, m, n;
	cin >> t;
	while (t--) {
		cin >> m >> n;
		cout << count(m, n) << endl;
	}
	return 0;
}
